# Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai).
# n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0).
# Find two lines, which together with x-axis forms a container,
# such that the container contains the most water.

# Note: You may not slant the container.

#time out
class Solution_1(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """

        s = [] #每个i的最大容量的集合
        n = len(height) #集合数量

        i = 1
        for h in height:
            print(i)
            startSpace = 0 #i左侧最大容量
            endSpace = 0 #i右侧最大容量

            #计算i右侧最大容量
            end = n - 1 #右侧游标
            while end >= i:
                if height[end] >= h: #找到右侧第一个高度大于i的坐标
                    endSpace = h * (end + 1 - i) #计算面积
                    break
                end -= 1

            start = 0 #左侧游标
            while start < i - 1:
                if height[start] >= h:
                    startSpace = h * (i - start - 1)
                    break
                start += 1

            #比较左右面积，取较大值
            s.append(max(endSpace, startSpace))
            i += 1

        return max(s)


#69 ms
class Solution_2(object):
    #根据左右游标计算面积
    def getArea(self, height, start, end):
        return min(height[start], height[end]) * (end - start)

    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """

        start = 0 #左侧游标
        end = len(height) - 1 #右侧游标

        result = 0 #最大面积
        startHeight = height[start] #最大面积左侧高度
        endHeight = height[end] #最大面积右侧高度

        #游标位于两端时面积
        result = self.getArea(height, start, end)

        #游标逐渐向中靠拢，直到两游标相遇
        while start < end - 1:
            if height[start] > height[end]: #如果左侧游标高度较大
                end -= 1 #右侧游标左移

                #找到第一个高度大于 目前最大面积右侧高度 的坐标
                if height[end] > endHeight:
                    newArea = self.getArea(height, start, end) #计算新面积
                    if newArea > result: #如果新面积大于目前记录的最大面积
                        endHeight = height[end] #记录新的最大面积右侧高度
                        result = newArea #更新最大面积
            else:
                start += 1

                if height[start] > startHeight:
                    newArea = self.getArea(height, start, end)
                    if newArea > result:
                        startHeight = height[start]
                        result = newArea

        return result



#test
solution = Solution_2()
result = solution.maxArea([2,3,4,5,18,17,6])

print("\n", "-----------------------------------------", "\n")
print(result)
print("\n", "-----------------------------------------", "\n")